package DFS;

/**
 *
 * 自己的二分图染色
 *
 * @Author: dust
 * @Date: 2019/11/18 16:27
 */
public class ERfengtu {

    private Graph G;
    private int[] visited;
    private int flag=1;
    private boolean isErfen;

    public ERfengtu(Graph G) {

        this.G=G;
        visited=new int[G.V()];
        for(int i=0;i<visited.length;i++){
            visited[i]=0;
        }
        isErfen=dfs(0);
    }

    public boolean isErfen(){
        return isErfen;
    }

    private boolean dfs(int v){
        flag=-flag;
        visited[v]=flag;
        for(int w:G.adj(v)){
            if(visited[w]==0){
                if(!dfs(w))
                    return false;
            }else if(visited[w]==visited[v]){
                return false;
            }else{
                continue;
            }
        }
        return true;
    }


    public static void main(String[] args) {
        Graph g=new Graph("g.txt");
        ERfengtu dfs=new ERfengtu(g);
        System.out.println(dfs.isErfen);
    }

}
